#include <string>
#include <vector>

using std::string;
using std::vector;

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }
        if (s3.length() == 0) {
            return true;
        }
        int size_i = s1.length() + 1;
        int size_j = s2.length() + 1;
        vector<vector<bool>> v;
        vector<bool> tmp;
        for (int i = 0; i < size_i; i++) {
            tmp = vector<bool>(size_j, true);
            v.push_back(tmp);
        }
        for (int i = 1; i < size_i; i++) {
            v[i][0] = v[i - 1][0] && (s1[i - 1] == s3[i - 1]);
        }
        for (int i = 1; i < size_j; i++) {
            v[0][i] = v[0][i - 1] && (s2[i - 1] == s3[i - 1]);
        }
        for (int i = 1; i < size_i; i++) {
            for (int j = 1; j < size_j; j++) {
                v[i][j] = (v[i - 1][j] && (s1[i - 1] == s3[i + j - 1])) || (v[i][j - 1] && (s2[j - 1] == s3[i + j - 1]));
            }
        }
        return v[size_i - 1][size_j - 1];
    }
};